package algorithm;

import sun.security.util.AuthResources_it;

import javax.xml.bind.annotation.W3CDomHandler;
import java.util.Arrays;

//最小生成树
//普利姆算法
//最小联通子图
public class Prim {
    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        final int MAX = 10000;
        int[][] weight = {
                {MAX, 5, 7, MAX, MAX, MAX, MAX, 2},
                {5, MAX, MAX, 9, MAX, MAX, 3},
                {7, MAX, MAX, MAX, 8, MAX, MAX},
                {MAX, 9, MAX, MAX, MAX, 4, MAX},
                {MAX, MAX, 8, MAX, MAX, 5, 4},
                {MAX, MAX, MAX, 4, 5, MAX, 6},
                {2, 3, MAX, MAX, 4, 6, MAX}
        };
        MGraph mGraph = new MGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.createGraph(mGraph, verxs, data, weight);
        minTree.show(mGraph);
        minTree.prim(mGraph,1);
    }


}

class MinTree {
    public void prim(MGraph graph, int v) {
        int[] visited = new int[graph.verxs];

        visited[v] = 1;
        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000;
        for (int k = 1; k < graph.verxs; k++) {

            //这个是确定每一次生成的子图，和那个结点的距离最近
            for (int i = 0; i < graph.verxs; i++) {//i表示未访问的结点
                for (int j = 0; j < graph.verxs; j++) {//j表示未被访问的结点
                    if (visited[i] == 1 && visited[j] == 0
                            && graph.weight[i][j] < minWeight) {
                        //替换minWeight
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
            visited[h2] = 1;
            minWeight=10000;
        }

    }

    public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
        for (int i = 0; i < verxs; i++) {
            graph.data[i] = data[i];
            for (int j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }

    }

    public void show(MGraph graph) {
        for (int[] arr : graph.weight) {
            System.out.println(Arrays.toString(arr));
        }
    }
}

class MGraph {
    int verxs;
    char[] data;
    int[][] weight;

    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}
